COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A98.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 13, 1989}
\leftline{\sevenrm Unpublished draft}\bigskip
\noindent{\bf Theorem}

Let $A$ be any set, $M$ a Turing machine with an A-oracle.  Let predicate 
$H(c, d)$ be true iff $c$ encodes a program for $M$ that accepts argument $d$.  
We show that no program for $M$ can compute $H$.

Suppose some program $P$ for $M$ did compute $H$.  We could build around it
a program $P↓2$ that, on argument $x$, uses a simulation of $P↓1$  to
determine $H(x, x)$.  Then if $H(x, x)$ were false it would halt in 
a rejecting state, and if $H(x, x)$ were false it would halt in an
accepting state.

Let $c↓2$ be the encoding of $P↓2$.  Look at what happens when $c↓2$ is taken
as the argument of $P↓2$.  If $H(c↓2, c↓2)$ is true, that implies that $P↓2$
accepts $c↓2$, but also that $P↓2$ rejects $c↓2$ (so does not accept $c↓2$.

If $H(c↓2, c↓2)$ is false, that implies that $P↓2$ does not accept $c↓2$, but 
also that it does accept $c↓2$.  Either way we have a contradiction, traceable
only to the assumption that there is a program for $M$ that computes $H$.

{\bf Corollary:}  There is no program for $M$ that determines for arguments
$c$ and $d$ whether $c$ encodes a program for $m$ that halts (whether accepting
or rejecting) on argument $d$.

{\bf Proof:}  If there were such a program, it could be used to compute
$H(c, d)$.  If the program does not halt, it does not accept.  If it
halts, it can safely be simulated until accepting or rejecting.  But we know
that no program for $M$ can compute $H(c, d)$, so no program for $M$ can
determine which programs for $M$ halt on which data.

The corollary is an example of what is called a {\it reducibility} argument.
If there is an algorithm to convert any question in a set $S↓1$ of questions, into
some question in a set $S↓2$, then a program that answers arbitrary
questions in $S↓2$ can be made into a program that answers arbitrary
questions in $S↓1$.  If there is no program that answers arbitrary questions
in $S↓1$, there can be no program that answers arbitrary questions in
$S↓2$.  In the jargon, if $S↓1$ is reducible to $S↓2$, and $S↓1$ is undecidable,
so is $S↓2$.  The standard tactic for proving a class of questions undecidable
is to reduce the class of halting problems to it.

Naturally, the preceding undecidability results carry over to Turing machines
without oracles, which are equivalent in most ways to Turing machines
with an oracle for the empty set.  (``Just say no'' is the oracle's motto.)

If $A$ is any oracle, let $B$ be the set of pairs $\langle c, d\rangle$ for
which program $c$ for an A-machine halts on argument $d$.  Then a B-program
can decide membership in $B$, which no A-program can do.  A B-program can
also decide membership in $A$.  Given argument $x$, to find whether $x\in A$,
the B-program constructs an A-program that, ignoring input, puts $x$ into an
oracle queue, tests whether $x\in A$, halts if $x \in A$, but loops if
$x\notin A$.  Then the B-program uses the B-oracle to deterine whether the
program it has constructed halts or not, which is to say, whether
$x\in A$ or not.

We conclude:  for any oracle A, there is an oracle B = J(A) such that
anything an A-program can do can be done by a B-program, but the B-program can
decide the halting problems of A-programs, which no A-program can do.  There
is no ``best'' oracle; for any oracle there is a better one, just as for
any number there is a bigger one.\bye